The present invention relates generally to wireless communication systems and, more particularly, to a system and method for modeling and analyzing complex issues in a wireless communication system.
The cellular industry has made phenomenal strides in commercial operations both in the United States and the rest of the world. Growth in major metropolitan areas has far exceeded expectations and is rapidly outstripping system capacity. If this trend continues, the effects of this industry""s growth will soon reach even the smallest markets. Innovative solutions are required to meet these increasing capacity needs as well as to maintain high quality service and avoid rising prices.
In addition to the challenges posed by the need for greater system capacity, the designers of future wireless communication systems have their own unique set of challenges. For example, in order to engineer efficient wireless systems, designers need to be able to quickly and accurately estimate the capacity of a wireless communication system and analyze its performance.
Conventional approaches to capacity estimation and performance analysis involve the use of analytical formulae, computer simulations, or classical numerical methods. The use of analytical formulae, however, generally necessitates unrealistic assumptions (e.g., ignoring redialing or abandoning behavior of wireless customers when estimating the capacity of a wireless system). Similarly, the use of computer simulations typically requires a substantial setup time and achieves a less accurate estimate. In addition, the use of classical numerical methods generally requires an amount of computation time that makes use of such methods impractical.
A class of analytical models exists, called xe2x80x9cmulti-dimensional birth-death models,xe2x80x9d that can be easily used to accurately model many capacity estimation and performance analysis issues. Unfortunately, the classical numerical approach to solving these models is well known as an excessively slow and frequently impractical approach for large systems.
FIG. 1 illustrates a general two-dimensional birth-death model 100 that can be used to model many capacity estimation and performance analysis issues. The two-dimensional birth-death model 100 includes several states 110. Each state represents how something is: its configuration, attributes, condition, or information content. For example, a state may represent a specific number of voice calls and a specific number of data calls occupying a channel in a wireless system at a given instance.
As illustrated, a system may transition from a first state to any of its nearest neighboring states. For example, a system may transition from state 110a to its neighboring state to the west, its neighboring state to the south, its neighboring state to the east, its neighboring state to the southwest, or its neighboring state to the southeast.
A two-dimensional birth-death model, such as model 100, can be used to analyze a variety of telecommunications issues, as well as other types of issues. For example, three areas of importance to designers of wireless systems that can be represented by two-dimensional birth-death models include analyzing wireless traffic in a system while taking into account the effects of redial traffic, analyzing wireless traffic in a system while taking into account the effects of handoff traffic, and analyzing the use of different priority schemes in a wireless system having both voice and data traffic.
Conventional approaches to estimating the capacity of a cell site, such as the use of analytical formulae, typically consider only the regular traffic at the cell site. Such approaches do not, however, take into account the effects of customers redialing in those situations when an original call to the cell site is blocked. In order to obtain a more accurate estimate of the capacity of the cell site, both regular traffic and redial traffic should be considered. A two-dimensional birth-death model may be used to estimate the capacity of a system having both types of traffic. One dimension of the model (e.g., the horizontal axis of the model 100 in FIG. 1) may be assigned to the number of channels in use in the cell site while the other dimension (e.g., the vertical axis of model 100) may be assigned to the number of customers who have been blocked, but may redial. By taking redial traffic into account when estimating a cell site""s capacity, a more accurate estimation may be obtained.
A two-dimensional birth-death model may also be used to analyze wireless traffic in a system while taking into account regular and handoff traffic. Typically, system designers treat both types of traffic the same in order to simplify system analyses. In order to increase customer satisfaction, however, regular traffic and handoff traffic should be treated differently. For example, from a customer satisfaction perspective, it is often better to block a customer attempting a new telephone call than to drop a customer in the middle of a telephone call. When analyzing such a system using a two-dimensional birth-death model, one dimension may be assigned to the number of new calls in the system and the other dimension to the number of hand-in calls. Such a model would allow system designers to analyze different types of reservation (or priority assignment) techniques.
Similarly, if a channel in a wireless system handles both voice and data traffic, it may be desirable to assign different levels of priority to the traffic types. A two-dimensional birth-death model could represent such a system. System designers could analyze the effects of the different levels of priority by assigning one dimension of the two-dimensional birth-death model to the number of voice calls in the system and the other dimension to the number of data calls in the system. As a result, a variety of priority schemes can be easily analyzed.
To analyze two-dimensional birth-death models, the steady state ergodic probability of a column vector being in the set of states ((j, 0), . . . , (j, n)) is defined as ej=(ej0, . . . , ejn)T, where ej0 is the probability of being in state (j, 0) and ejn is the probability of being in state (j, n), and the infinitesimal generator of the probability flow from (j, i) to (jxe2x88x921, k) to be [xcexdjxe2x88x92]i,k, from (j, i) to (j+1, k) to be [xcexdj+]i,k, from (j, i) (j, k) to be [xcexdj0]i,k if ixe2x89xa0k and the total probability flow out of (j, i) to be xe2x88x92[xcexdj0]i,i, i.e., xe2x88x92[xcexdj0]i,i=xcexa3k([xcexdj+]i,k+"khgr"(ixe2x89xa0k)[xcexdj0]i,k+[xcexdjxe2x88x92]i,k) so
(xcexdj++xcexdj0+xcexdjxe2x88x92)1=0xe2x80x83xe2x80x83(1)
where xcexdj0, xcexdj0, and xcexdjxe2x88x92, are matrices, and 1 and 0 are vectors consisting of only 1""s and 0""s, respectively.
Two-dimensional birth-death equations have a steady state solution satisfying
"khgr"{jxe2x89xa00}ejxe2x88x921Txcexdjxe2x88x921++ejtxcexdj0+"khgr"{jxe2x89xa0n}ej+1Txcexdj+1xe2x88x92=0 j=0, . . . , m,xe2x80x83xe2x80x83(2)
and                                           ∑                          j              =              0                        m                    ⁢                      xe2x80x83                    ⁢                                                    e                _                            j              T                        ⁢                          1              _                                      =        1.                            (        3        )            
In general, when the condition of the subscript associated with "khgr" is true, the value of "khgr" equals 1 and equals 0 otherwise. In equation 2, therefore, X{jxe2x89xa00} equals 1 when jxe2x89xa00 and equals 0 when j=0.
To simplify future notation, assume
xcexd0xe2x88x92=xcexdm+=0.xe2x80x83xe2x80x83(4)
where xcexd0xe2x88x92 and xcexdm+ are (m+1xc3x97m+1) matrices and 0 is a matrix consisting only of 0""s. Note that equations (2) and (3) are the solution to equations
eTxcexd=0
and
eT1=1
where eT=(e0T, e1T, . . . ,enT) is a 1xc3x97(n+1)(m+1) vector and   v  =      (                                        v            0            0                                                v            0            +                                    0                          0                          ⋯                          0                          0                                                  v            1            -                                                v            1            0                                                v            1            +                                    0                          ⋯                          0                          0                                      0                                      v            2            -                                                v            2            0                                                v            2            +                                    ⋯                          0                          0                                      0                          0                                      v            3            -                                                v            3            0                                    ⋯                          0                          0                                      0                          0                          0                                      v            4            -                                    ⋯                          0                          0                                      0                          0                          0                          0                          ⋯                                      v                          m              -              2                        +                                    0                                      ⋯                          ⋯                          ⋯                          ⋯                          ⋯                                      v                          m              -              1                        0                                                v                          m              -              1                        +                                                0                          0                          0                          0                          ⋯                                      v            m            -                                                v            m            0                                )  
is an (n+1)(m+1)xc3x97(n+1)(m+1) block tridiagonal matrix where each block is itself a (n+1)xc3x97(n+1) tridiagonal matrix. This special structure is referred to hereinafter as a xe2x80x9crecursively tridiagonalxe2x80x9d structure. A recursively tridiagonal matrix, therefore, is a matrix that is block tridiagonal, and each block is block tridiagonal, and each of these blocks is block tridiagonal, etc.
As illustrated, the matrix xcexd consists of three diagonal lines of blocks. For example, blocks xcexd00, xcexd10, xcexd20, and xcexd30 make up the main diagonal of matrix xcexd. The other diagonals that exist just above and just below the main diagonal consist of blocks xcexd0+, xcexd1+, and xcexd2+ and blocks xcexd1xe2x88x92, xcexd2xe2x88x92, and xcexd3xe2x88x92, respectively. Each of the blocks of matrix xcexd, as set forth above, has a tridiagonal structure. It is apparent from the structure of matrix xcexd that a large number of zeros exist and that they exist in regular locations (i.e., to the northeast and southwest of the three diagonal lines of blocks).
Linear equations eTxcexd=0 and eT1=1 may be solved using a variety of numerical approaches, the most common being the use of Gaussian elimination. Gaussian elimination requires on the order of (m3xc3x97n3) multiplication operations for an (mnxc3x97mn) matrix. Therefore, for example, for a matrix where the values of m and n are each 100, 1xc3x971012 multiplication operations would be necessary using Gaussian elimination. Consequently, as the number of rows and/or columns of the matrix increases, the number of multiplication operations increases dramatically. As such, Gaussian elimination proves to be an extremely slow solution to the performance analysis and capacity estimation of large telecommunications systems.
As an alternative to the use of Gaussian elimination, a block Gaussian algorithm may be used to solve two-dimensional birth-death equations. The block Gaussian algorithm exploits the fact that the xcexd matrix is block tridiagonal (i.e., it exploits the fact that there are a large number of zeros and that they are in regular locations in the matrix), but does not exploit the fact that each of the blocks in the matrix xcexd is tridiagonal. The number of multiplication operations needed to solve a two-dimensional birth-death equation using the block Gaussian algorithm is on the order of (mxc3x97n3). Consequently, use of a block Gaussian algorithm greatly reduces the number of multiplication operations needed in comparison to the Gaussian elimination when a large value of m exists. However, this algorithm is still an extremely slow solution to the performance analysis and capacity estimation of large telecommunications systems.
Therefore, there exists a need for a system and method that quickly and accurately solves multi-dimensional birth-death equations.
Systems and methods consistent with the present invention address this need by providing a process that reduces the number of multiplication operations needed for solving multi-dimensional birth-death equations.
In accordance with the purpose of the invention as embodied and broadly described herein, a method consists of selecting a first group of states from a multi-dimensional birth-death model and determining a relationship between the non-selected states and this first group of states. Thereafter, the method calculates the probabilities of being in the first group of states. Then, the method calculates the probabilities of being in the non-selected states using the relationship between the non-selected states and the first group of states and the calculated probabilities of the first group of states. The method solves the multi-dimensional birth-death model using the calculated probabilities of the first group of states and the non-selected states.